package com.base.dp;

public class Rob {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        Rob rob = new Rob();
        TreeNode root = new TreeNode(3);
        TreeNode left = new TreeNode(2);
        TreeNode r = new TreeNode(3);
        left.right = r;
        TreeNode right = new TreeNode(3);
        TreeNode rr = new TreeNode(1);
        right.right = rr;
        root.left = left;
        root.right = right;
        System.out.println(rob.rob(root));
    }

    /**
     * 打劫这个节点，那么就不能打劫它的左右子节点。
     * 不打劫这个节点，那么我们可以选择打劫或不打劫它的左右子节点。
     * 为了解决这个问题，我们可以定义一个递归函数，该函数返回两个值：
     *
     * 假设打劫当前节点，能够得到的最大金额。
     * 假设不打劫当前节点，能够得到的最大金额。
     * 对于每个节点，我们可以递归地计算它的左右子节点的这两个值，然后根据这两个值来更新当前节点的两个值。
     * @param root
     * @return
     */
    public int rob(TreeNode root) {
        int[] result = robSub(root);
        return Math.max(result[0], result[1]);

    }

    private int[] robSub(TreeNode root) {
        if (root == null) return new int[2];

        // 递归计算左右子树的值
        int[] left = robSub(root.left);
        int[] right = robSub(root.right);

        int[] result = new int[2];

        // 打劫当前节点，则不能打劫左右子节点
        result[0] = root.val + left[1] + right[1];

        // 不打劫当前节点，则可以打劫或不打劫左右子节点
        result[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        return result;
    }




}
